package cn.cool;


import java.util.Scanner;

public class Main2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        while (T-- > 0) {
            int n = scanner.nextInt();
            scanner.nextLine(); // 吃掉空行
            int[][] grid = new int[n][n];
            for (int i = 0; i < n; i++) {
                String row = scanner.nextLine();
                String[] r = row.split(" ");
                for (int j = 0; j < n; j++) {
                    grid[i][j] = Integer.parseInt(r[j]);
                }
            }

            long[][][] d = new long[n][n][2];
            // [0] 不拿
            // [1] 拿
            for (int i = n - 1; i >= 0; i--) {
                for (int j = n - 1; j >= 0; j--) {
                    // 不拿
                    if (i >= n - 1) {
                        d[i][j][0] = 0;
                    } else {
                        d[i][j][0] = Math.max(d[i + 1][j][0], d[i + 1][j][1]);
                    }

                    d[i][j][1] = grid[i][j];
                    if (j < n - 1) {
                        d[i][j][1] += Math.max(Math.max(d[i][j + 1][0], d[i][j + 1][1]), 0);
                    }
                }
            }
            System.out.println(Math.max(d[0][0][0], d[0][0][1]));
        }
    }
}


















































